package 栈.middle;

/**
 * @author Lw中
 * @date 2020/10/20 9:48
 */
public class SiJiuSi {

    /**
     * LWZ TODO : 2020/10/20 代码有点迷
     *
     */

    /**
     * 目标和
     * 使用枚举方法
     */
    static int count = 0;
    public static int findTargetSumWays(int[] nums, int S) {
        calculate(nums, 0, 0, S);
        return count;
    }

    /**
     * 递归计算和为S的情况次数
     * @param nums
     * @param i
     * @param sum
     * @param S
     */
    public static void calculate(int[] nums, int i, int sum, int S) {
        if (i == nums.length) {
            if (sum == S) {
                count++;
            }
        } else {
            calculate(nums, i + 1, sum + nums[i], S);
            calculate(nums, i + 1, sum - nums[i], S);
        }
    }

    public static void main(String[] args) {
        int[] arr = {1,1,1,1,1};
        int targetSumWays = findTargetSumWays(arr, 3);
        System.out.println(targetSumWays);
    }

}
